package graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class canFinish {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 记录每个课程的入度关系，以及结果集和各个课程的链接情况
        int[] inDegree = new int[numCourses];
        List<List<Integer>> umap = new ArrayList<>(numCourses);
        // 完成初始化
        for (int i = 0; i < numCourses; i++) {
            List<Integer> subList = new ArrayList();
            umap.add(subList);
        }
        // m*2的二维数组
        for (int i = 0; i < prerequisites.length; i++) {
            inDegree[prerequisites[i][0]]++;

            List<Integer> subList = umap.get(prerequisites[i][1]);

            subList.add(prerequisites[i][0]);
            umap.set(prerequisites[i][1], subList);

        }
        List<Integer> rs = new ArrayList<>(numCourses);
        Deque<Integer> queue = new ArrayDeque();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                rs.add(i);
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            // 获取起点。然后删除起点
            Integer index = queue.poll();
            // 修改其他节点的入度
            List<Integer> outDegree = umap.get(index);
            for (Integer item : outDegree) {
                inDegree[item]--;
                if (inDegree[item] == 0) {
                    queue.offer(item);
                    rs.add(item);
                }
            }
        }

        if (rs.size() == numCourses) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        int[][] grid = new int[][] {
                { 1, 0 },
                
        };
        canFinish obj = new canFinish();
        boolean nums = obj.canFinish(2, grid);
        System.out.println(nums);
    }
}
